package com.hqq.exercise.sort_search;

import org.omg.CORBA.PUBLIC_MEMBER;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * Sort 排序算法
 * Created by heqianqian on 2017/8/15.
 */
public class Sort {

    private static final Logger LOGGER = LoggerFactory.getLogger(Sort.class);

    //选择排序

    /**
     * 堆排序
     */
    public static void heapSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        initMaxHeap(array);
        int temp;
        for (int i = array.length - 1; i >= 0; i--) {
            //每次交换第一个元素和最后一个元素 再调整成最大堆
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            createMaxHeap(array, i, 0);
        }
    }

    /**
     * 创建最大堆
     */
    private static void initMaxHeap(int[] array) {
        for (int i = (array.length - 1) / 2; i >= 0; i--) {//从第一个非叶子节点开始调整
            createMaxHeap(array, array.length, i);
        }
    }

    private static void createMaxHeap(int[] array, int length, int index) {
        int rootIndex = index;//当前要调整最大堆的根节点
        int childIndex = 2 * index + 1;//左孩子节点

        int temp = array[rootIndex];
        boolean flag = true;

        while (childIndex < length && flag) {
            if (childIndex < length - 1 && array[childIndex] < array[childIndex + 1]) {
                childIndex++;//选择左右子节点中的较大者
            }
            if (temp > array[childIndex]) {//当前已经满足最大堆
                flag = false;
            } else {//子节点上移
                array[rootIndex] = array[childIndex];
                rootIndex = childIndex;
                childIndex = 2 * rootIndex + 1;//继续往下遍历
            }
        }
        array[rootIndex] = temp;
    }

    //交换排序

    /**
     * 冒泡排序
     *
     * @param array 待排序数组
     */
    public static void bubbleSort(int[] array) {
        boolean flag = false;//用来表示当前次排序有无交换元素
        for (int i = 1; i < array.length && !flag; i++) {
            flag = true;
            for (int j = 0; j < array.length - i; j++) {
                if (array[j] > array[j + 1]) {
                    flag = false;
                    switchNumber(array, j, j + 1);
                }
            }
        }
    }

    /**
     * 双指针快排
     * [默认以起始节点为基数]
     */
    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        partition(array, 0, array.length - 1);
    }

    private static void partition(int[] array, int start, int end) {
        if (start >= end) {//递归出口 左右指针重合
            return;
        }
        int base = array[start];//默认选择第一个元素为基准元素
        int leftIndex = start;//左指针
        int rightIndex = end;//右指针

        while (leftIndex != rightIndex) {
            while (leftIndex < rightIndex && array[rightIndex] >= base) {//从右往左寻找比基准元素小的元素
                rightIndex--;
            }

            while (leftIndex < rightIndex && array[leftIndex] <= base) {//从左往右找比基准元素大的元素
                leftIndex++;
            }

            if (leftIndex < rightIndex) {//交换两个元素
                int temp = array[leftIndex];
                array[leftIndex] = array[rightIndex];
                array[rightIndex] = temp;
            }
        }
        //当前轮排序结束 将基准元素和指针元素交换
        array[start] = array[leftIndex];
        array[leftIndex] = base;

        //递归排序
        partition(array, start, leftIndex - 1);
        partition(array, leftIndex + 1, end);
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 1, 2, 5};
        int[] result = mergeSort(array);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 归并排序
     */
    public static int[] mergeSort(int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("Wrong Array!");
        }
        int[] result = new int[array.length];
        mergeSort(array, 0, array.length - 1, result);
        return result;
    }


    /**
     * 归并排序
     */
    private static void mergeSort(int[] array, int start, int end, int[] result) {
        if (start < end) {//拆分数组元素 直到每个数组的大小为1
            int mid = (start + end) / 2;
            mergeSort(array, start, mid, result);
            mergeSort(array, mid + 1, end, result);
            //合并两个子数组
            mergeArray(array, start, mid, end, result);
        }
    }

    /**
     * 合并两个子数组
     */
    private static void mergeArray(int[] array, int start, int mid, int end, int[] result) {
        int aIndex = start, bIndex = mid + 1, rIndex = 0;
        while (aIndex <= mid && bIndex <= end) {
            //只要两个子数组非空 就放入两个数组种较小的那个元素
            if (array[aIndex] < array[bIndex]) {
                result[rIndex++] = array[aIndex++];
            } else {
                result[rIndex++] = array[bIndex++];
            }
        }
        /*当一个数组为空 将另一个数组的元素全部按照顺序取出*/
        while (aIndex <= mid) {
            result[rIndex++] = array[aIndex++];
        }
        while (bIndex <= end) {
            result[rIndex++] = array[bIndex++];
        }
        //最后把排好序的元素复制合并到原数组中
        System.arraycopy(result, 0, array, start, rIndex);
    }

    /**
     * 合并两个数组
     * 前提是两个数组必须是有序的
     */
    private static int[] mergeArray(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int aIndex = 0, bIndex = 0, rIndex = 0;
        while (aIndex < a.length && bIndex < b.length) {
            //两个数组都存在元素的情况下 取较小的那个元素
            if (a[aIndex] < b[bIndex]) {
                result[rIndex++] = a[aIndex++];
            } else {
                result[rIndex++] = a[bIndex++];
            }
        }
        //当某个数组为空时 直接将另一个元素中剩下的元素按序取出即可
        while (aIndex < a.length) {
            result[rIndex++] = a[aIndex++];
        }
        while (bIndex < b.length) {
            result[rIndex++] = a[bIndex++];
        }
        return result;
    }


    /**
     * 基数排序
     * <p>
     * 如果需要对0-100内的若干个数据排序 那么初始化101个元素的数组
     * 统计数组中每个值为i的元素出现的次数，存入数组的第i项
     * 最后对所有的计数累加并打印
     *
     * @param array 待排序数组
     */
    public static void radixSort(int[] array) {
        int maxNumber = getMaxNumber(array);
        int[] bucket = new int[maxNumber + 1];
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        for (int i = 0; i < bucket.length; i++) {
            for (int j = 0; j < bucket[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }

    /**
     * 获取数组中的最大值
     */
    private static int getMaxNumber(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        return max;
    }

    /**
     * 交换数组中两个元素的值
     */
    private static void switchNumber(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}
